/**
 * @file     detectCycle.js
 * @brief    [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
 * @author   Zhu
 * @date     2022-03-17 14:08
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    let slow = head;
    let fast = head;
    do {
        slow = slow?.next ?? null;
        fast = fast?.next?.next ?? null;
    } while (slow !== fast && fast !== null);

    if (fast === null) return null;

    fast = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return fast;
};

var detectCycle = function (head) {
    let slow = head;
    let fast = head;

    while (fast !== null) {
        fast = fast?.next?.next ?? null;
        slow = slow?.next ?? null;
        if (fast !== null && fast === slow) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return slow;
        }
    }

    return null;
};
